package com.leetcode;

/**
 * @Classname Leetcode188
 * @Description TODO
 * @Date 2021-08-01 20:56
 * @Created by darrren
 */
public class Leetcode188 {

    //from : https://time.geekbang.org/course/detail/100019701-69782
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;

        int n = prices.length;
        k = Math.min(k, n / 2);

        int[][][] dp = new int[n][2][k + 1];

        for (int j = 0; j <= k; j++) {
            // 第 1 天买入 - 卖出循环 K 次之后不再买入，所以初始值为 0
            dp[0][0][j] = 0;
            // 第 1 天买入 - 卖出循环 K 次之后又买入，所以初始值为 -prices[0]
            dp[0][1][j] = -prices[0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                //这里存在同一天买入又卖出的情况，不过收益是0，因此可以省略
                //之前没有买入股票 或者 之前买入了一只股票又卖出了
                //买入时增加交易次数，卖出时交易次数不变,因此 j-1 代表上一次交易的次数
                dp[i][0][j] = (j != 0) ? Math.max(dp[i - 1][0][j], dp[i - 1][1][j - 1] + prices[i]) : dp[i-1][0][0];
                //买入时增加交易次数，卖出时交易次数不变,因此 j 不变
                dp[i][1][j] = Math.max(dp[i - 1][1][j], dp[i - 1][0][j] - prices[i]);
            }
        }

//        int max = Integer.MIN_VALUE;
//        for (int i = 0; i <= k; i++)
//            max = Math.max(max, dp[n - 1][0][i]);
//        return max;
        return dp[n - 1][0][k];
    }
    /*
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;

        int n = prices.length;
        k = Math.min(k, n / 2);
        int[][][] mp = new int[n][2][k + 1];
        for (int i = 0; i <= k; i++) {
            // 第 1 天买入 - 卖出循环 K 次之后不再买入，所以初始值为 0
            mp[0][0][i] = 0;
            // 第 1 天买入 - 卖出循环 K 次之后又买入，所以初始值为 -prices[0]
            mp[0][1][i] = -prices[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                mp[i][0][j] = j != 0 ? Math.max(mp[i - 1][1][j - 1] + prices[i], mp[i - 1][0][j]) : mp[i - 1][0][j];
                mp[i][1][j] = Math.max(mp[i - 1][0][j] - prices[i], mp[i - 1][1][j]);
            }
        }
        return mp[n-1][0][k];
    }
    */
    public static void main(String[] args) {
        Leetcode188 leetcode = new Leetcode188();
        int[] prices = {1,2,4,2,5,7,2,4,9,0};
        System.out.println(leetcode.maxProfit(4, prices));
    }
}
